//
//  main.cpp
//  hashtable
//
//  Created by chenyh on 2021/2/5.
//

#include <iostream>
/*
 散列表的定义
 为了实现不经比较就能查找到指定元素，需要在结构的元素存储位置和元素值之间建 立一种映射关系，我们称这种关系为哈希函数 f，称元素值为关键字。关系 f 的作用就是使 每一个关键字与表中的一个元素的存储位置相对 应。比如说，我们需要在散列表中查找一个值为
   Value 的元素，那么关键字就是 value，根据哈希函 数 f(k)可以直接计算出值为 value 的元素的存储位置， 从而找出这个元素而不需要进行值的比较。这种思 想称为散列思想。
 散列函数是将关键字映射为散列表中适当位置的函数(关系式)。通过散列函数计算 出的元素的存储地址称为散列地址。
 那么设计 一个好的散列函数的标准是什么呢?
 一个好的散列函数必须具备两个特点:较少的冲突和函数是均匀的。
  冲突:是散列表中的一个重要概念，也是构造散列表时要尽力避免的状况。它是 指两个不同的关键字经过散列函数映射到了同一个地址，即 value1≠value2，但是
 f(value1) = f(value2)。冲突给散列表的构建和数据的存储造成了混乱，所以我们在
 设计散列函数时，应该尽量减少冲突的发生。
  均匀性:如果对关键字集合中的任何一个关键字，通过散列函数映射到地址集合
 的任何一个地址的概率是相等的，我们就说这个散列函数是均匀的。
 常用的散列函数构造方法有以下几种。
 1.直接定址法
 直接定址法就是取关键字的某个线性函数为散列函数。
 f(v) = a×v+b(a,b 为常数)
 例如，关键字集合{20,40,60,80}，选取线性函数 f(v) = v/10 为线性函数，
 这种设计散列函数的方式最简单，一般是用于事先知道关键字集合，且关键字集合不
 大并且连续性好。
 
 2.除留余数法
 散列函数为:
 根据经验，p 一般取小于或等于表长(尽量接近表长)的最小素数为宜。此法不需要
 事先知道关键字集合，是最常用的构造散列函数的方法。
 F(v) = v mod p (p为常数)
 
 3.平方取中法
 将关键字平方后，根据散列表的设计大小，取平方结果的中间若干位作为散列地址， 这是一种较为常用的方法。一般来说，在构造散列函数的时候并不一定知道关键字的全部 情况，但是一个数平方之后，值的中间几位数字与原数的每一位都相关，这就使得使用随 机分布的关键字得到的散列地址也是随机的。例如，如果散列地址取 2 位，则关键字 345 的散列地址为:
 3452 = 119025，取 90 为其散列地址。
 
 散列表在查找时有个很大的缺点就是冲突。所以我们先来 看看如何处理冲突问题。
 常用的冲突的处理方法有以下几种。
 1.开放定址法
 在数据存取时，一旦产生了冲突，就寻找下一个空白的散列地址。
 Fi = (f(v)+di)mod n i=1,2,..,v(v≤n-1)
 其中:n 为散列表长度，f(v)为散列函数，di 为增量序列。
 增量序列有 3 种确定方法:
 一， 线性探测法:从发生冲突位置的下一个位置开始依次探测，d=1,2,3,...n-1 探测空
 白的地址;
 二， 二次探测再散列:di = 1,-1,2 平方,-2平,-3平 ,3 平,...,±v (v≤n/2);
 三，伪随机探测:di 是一个伪随机数序列。
 
 2.链地址法
 将所有具有相同散列地址的不同关键字(同义词)存放 在一个单链表中，这些单链表称为同义词子表，散列表中存 储的是这些单链表的头指针。如果有 n 个关键字存储在长度 为 m 的散列表中，则同义词子表的平均长度为 n/m。
 例如，有关键字集合{47,7,29,11,16,92}，取 f(v)=v mod 11 为散列函数，用链地址法处理冲突，所构造的散列表如图 1-22 所示。
 3.公共溢出区法
 将散列表分为基本表和溢出表两部分，基本表与溢出表
 将发生冲突的关键字存在溢出表中。查找时， 对给定的关键字计算散列地址，然后与基本表中相应位置的元素进行比较，如果一致则查 找成功，如果不一致，则去溢出表中顺序查找。这种方法会产生比较行为。
 了解了冲突的处理方式之后，下面来看看散列表的查找过程。我们以开放定址法为处 理冲突的方式来演示散列表的查找过程，并用 C++语言实现，
 */
#include "HashTable.hpp"
int main(int argc, const char * argv[]) {
    HashTable<int> hashtable = HashTable<int>(13);
    hashtable.insertHash(66);
    hashtable.insertHash(32);
    hashtable.insertHash(98);
    hashtable.insertHash(478);
    hashtable.insertHash(11);
    hashtable.insertHash(23);
    hashtable.insertHash(43);
    hashtable.insertHash(55);
    hashtable.insertHash(67);
    hashtable.insertHash(108);
    hashtable.insertHash(230);
    hashtable.insertHash(223);
    hashtable.insertHash(10);
    //输出元素
    std::cout<<"表中的元素为：";
    for (int i = 1; i <= 13; i++) {
        std::cout<<hashtable.getData(i)<<"  ";
    }
    std::cout<<std::endl;
    std::cout<<"元素55的位置："<<hashtable.searchHash(55)<<std::endl;    
    return 0;
}
